package leetcode_500;

import helpclass.TreeNode;

/**
 *@author 周杨
 *DeleteNodeInABST_450 删除一个二叉搜索树中的某个节点  
 *describe:删除该节点最左下角的节点 注意根节点的特殊情况 AC 80%
 *2018年8月22日 下午1:34:55
 */
public class DeleteNodeInABST_450 {
	public static void main(String[] args) {
		DeleteNodeInABST_450 test=new DeleteNodeInABST_450();
		TreeNode root=new TreeNode(5);
		root.left=new TreeNode(3);
		root.right=new TreeNode(6);
		root.left.left=new TreeNode(2);
		root.left.right=new TreeNode(4);
		root.right.right=new TreeNode(7);
		
	}
	
	/**
	 * describe:AC 80%
	 * 2018年8月22日 下午2:04:36
	 */
	public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode cur = root, parent = null;
        
        while(cur != null){//找到这个点 和 pre
            if(cur.val == key)  break;
            parent = cur;
            if(cur.val > key)   cur = cur.left;
            else cur = cur.right;
        }
        if(cur == null) return root;//没有找到
        if(parent == null)   return del(root);//删除根节点
        if(parent.left != null && parent.left.val == key)
            parent.left = del(cur);
        else
            parent.right = del(cur);
        return root;
    }
    
    private TreeNode del(TreeNode node){//调整这颗二叉搜索树 并删除root
        if(node.left == null && node.right == null)
            return null;
        if(node.left == null || node.right == null){//只要有一颗子树为空 立马返回另外一颗子树
            return node.left == null ? node.right : node.left;
        }
        TreeNode cur = node.right, parent = node;//去找最左下角
        while(cur.left != null){
            parent = cur;
            cur = cur.left;
        }
        node.val = cur.val;
        if(parent == node)
            node.right = cur.right;
        else
            parent.left = cur.right;
        return node;
    }
	
	
	/**
	 * describe:不知道哪里错了。。。
	 * 2018年8月22日 下午1:58:26
	 */
	public TreeNode deleteNode1(TreeNode root, int key) {
        if(root==null)
        	return null;
        TreeNode pre=find(root,key,null);//可能找不到
        if(pre!=null) {
        	if(pre.left==null&&pre.right==null)
        		return root;
        }
        TreeNode node=pre==null?root:pre.left==null?pre.right:pre.left.val==key?pre.left:pre.right;
        if(node.left==null) {//没有左子树
        	if(pre==null) {//剪掉的是根节点
        		return root.right;
        	}
        	else {
        		if(pre.left.val==key)
					pre.left=node.right;
        		else
        			pre.right=node.right;
				return root;
        	}
        }
        TreeNode lefter=node,preLeft=pre;//找到最左下角的那个节点
        while(lefter.left!=null) {
        	preLeft=lefter;
        	lefter=lefter.left;
        }
        preLeft.left=null;//剪掉
        lefter.left=node.left;
        lefter.right=node.right;
        if(pre!=null) {//剪掉的并非是根节点
        	if(pre.left.val==key)
        		pre.left=lefter;
        	else 
        		pre.right=lefter;
        	return root;
        }
        else {
        	return lefter;
        }
    }
	
	public TreeNode find(TreeNode root,int key,TreeNode pre) {
		if(root==null)
            return pre;
		if(key==root.val)
			return pre;
		if(root.val>key) {
			pre=root;
			return find(root.left, key, pre);
		}
		pre=root;
		return find(root.right,key,pre);
	}
	
}
